package code.classic150on2025;

import utils.ListNode;

import java.util.PriorityQueue;

public class ThePartition {
    // 148. 排序链表
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode rightList = slow.next;
        slow.next = null;
        ListNode leftSorted = sortList(head);
        ListNode rightSorted = sortList(rightList);
        ListNode newHeadPre = new ListNode();
        ListNode node = newHeadPre;
        while (leftSorted != null && rightSorted != null) {
            if (leftSorted.val < rightSorted.val) {
                node.next = leftSorted;
                node = node.next;
                leftSorted = leftSorted.next;
            } else {
                node.next = rightSorted;
                node = node.next;
                rightSorted = rightSorted.next;
            }
        }
        if (leftSorted != null) {
            node.next = leftSorted;
        }
        if (rightSorted != null) {
            node.next = rightSorted;
        }
        return newHeadPre.next;
    }

    // 427. 建立四叉树
    public NodePrev2 construct(int[][] grid) {
        int n = grid.length;
        return partition427(grid, 0, 0, n);
    }

    private NodePrev2 partition427(int[][] grid, int beginx, int beginy, int len) {
        if (len == 1)
            return new NodePrev2(grid[beginx][beginy] == 1, true);

        NodePrev2 topLeft = partition427(grid, beginx, beginy, len / 2);
        NodePrev2 topRight = partition427(grid, beginx, beginy + len / 2, len / 2);
        NodePrev2 bottomLeft = partition427(grid, beginx + len / 2, beginy, len / 2);
        NodePrev2 bottomRight = partition427(grid, beginx + len / 2, beginy + len / 2, len / 2);

        if (topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf
                && topRight.val == topLeft.val && topLeft.val == bottomLeft.val && bottomLeft.val == bottomRight.val) {
            // 如果当前方块的四个子方框都是叶子并且值都一样，那么当前方框也是叶子
            return new NodePrev2(topLeft.val, true);
        } else {
            // 否则当前节点不是叶子，赋值四个子节点
            return new NodePrev2(false, false, topLeft, topRight, bottomLeft, bottomRight);
        }
    }

    // 23. 合并 K 个升序链表
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.val, o2.val));
        for (ListNode node : lists) {
            if (node != null)
                pq.add(node);
        }
        ListNode preHead = new ListNode();
        ListNode node = preHead;
        while (!pq.isEmpty()) {
            ListNode now = pq.poll();
            node.next = now;
            node = node.next;
            now = now.next;
            if (now != null) {
                pq.add(now);
            }
        }
        return preHead.next;
    }
}

class NodePrev2 {
    public boolean val;
    public boolean isLeaf;
    public NodePrev2 topLeft;
    public NodePrev2 topRight;
    public NodePrev2 bottomLeft;
    public NodePrev2 bottomRight;


    public NodePrev2() {
        this.val = false;
        this.isLeaf = false;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }

    public NodePrev2(boolean val, boolean isLeaf) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }

    public NodePrev2(boolean val, boolean isLeaf, NodePrev2 topLeft, NodePrev2 topRight, NodePrev2 bottomLeft, NodePrev2 bottomRight) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = topLeft;
        this.topRight = topRight;
        this.bottomLeft = bottomLeft;
        this.bottomRight = bottomRight;
    }
}